package com.lsa.letcode.the53.maxSubarray;

public class Solution {
	private static final String FORMAT_STR = "%5s";
	static boolean PRINT_BOUNDS = false;
	
	void printBounds(){
		PRINT_BOUNDS = true;
	}
	
	void stopPrintBounds(){
		PRINT_BOUNDS = false;
	}
	
    public int maxSubArray(int[] nums) {
    	int n = nums.length;
    	if (n == 0){
    		return 0;
    	}
        int[][] dp = new int[nums.length][nums.length];
        
        for (int i = 0; i < n; i++) {
        	dp[i][i] = nums[i];
		}
        
        int max = nums[0];
        int maxI = -1;
        int maxJ = -1;
        for (int l = 2; l < n + 1; l++) {
			for (int i = 0; i < n - l + 1; i++) {
				int j = l + i - 1;
				dp[i][j] = dp[i][j - 1] + nums[j];
				if (dp[i][j] > max) {
					max = dp[i][j];
					maxI = i;
					maxJ = j;
				}
			}
		}
        if (PRINT_BOUNDS) {
        	for (int i = 0; i < n; i++) {
				System.out.print(String.format(FORMAT_STR, i));
			}
        	System.out.println();
        	for (int i = 0; i < n; i++) {
        		System.out.print(String.format(FORMAT_STR, nums[i]));
        	}
        	System.out.println();
        	for (int i = 0; i < n; i++) {
        		System.out.print(String.format(FORMAT_STR, (i == maxI || i == maxJ)? "|" : ""));
			}
        	System.out.println();
        	System.out.println(String.format("%s %s", maxI, maxJ));
        	System.out.println("---------------------------");
        }
        return max;
    }
}